/*
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
You should return [1,2,3,6,9,8,7,4,5].
*/

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        vector<int> res;
        if (!matrix.size()) return res;
        int x = 0, y = 0, m = matrix.size(), n = matrix[0].size();
        while (m>1 && n>1) {
            // scan through right, down, left, up
            for (int steps=n-1;steps>0;steps--) res.push_back(matrix[x][y++]);
            for (int steps=m-1;steps>0;steps--) res.push_back(matrix[x++][y]);
            for (int steps=n-1;steps>0;steps--) res.push_back(matrix[x][y--]);
            for (int steps=m-1;steps>0;steps--) res.push_back(matrix[x--][y]);
            x++;y++; // make a down right turn
            m -= 2; n -= 2;
        }
        if (m==1) {for (int steps=n; steps>0; steps--) res.push_back(matrix[x][y++]);}
        else if (n==1) {for (int steps=m; steps>0; steps--) res.push_back(matrix[x++][y]);}
        return res;
    }
};
